#include <stdio.h>
#include <limits>

/*****边类*****/
class Edge
{
public:
    int from, to, weight;
    Edge()
    {
        from = -1;
        to = -1;
        weight = 0;
    }
    Edge(int f, int t, int w)
    {
        from = f;
        to = t;
        weight = w;
    }
};
/*****边类*****/

/*****图类*****/
class Graph
{
public:
    int numV;       //顶点的个数
    int numE;       //边的个数
    bool *mark;     //访问标记
    int *in_degree; //数组：每个顶点的入度

    Graph(int numV_input) //构造函数
    {
        numV = numV_input;
        numE = 0;
        in_degree = new int[numV];
        mark = new bool[numV];
        for (int i = 1; i <= numV; i++)
        {
            mark[i - 1] = false;
            in_degree[i - 1] = 0;
        }
    }

    ~Graph() //析构函数
    {
        delete[] mark;
        delete[] in_degree;
    };

    bool isE(Edge e)
    {
        // weight为0代表无权重的图
        // if (e.weight >= 0 && e.weight < INFINITY && e.to >= 0)
        if (e.weight >= 0 && e.to >= 0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};
/*****图类*****/

/*****邻接表元素类*****/
typedef struct ADJ_List_unit
{
    int terminal_vertex; //终点
    int weight;          //权重
} ADJ_List_unit;
/*****邻接表元素类*****/

/*****通用单链表结点类*****/
template <class Elem>
class Link //链表元素类
{
public:
    Elem element;
    Link *next;

    Link(const Elem &elemval, Link *nextlink = NULL)
    {
        element = elemval;
        next = nextlink;
    }

    Link(Link *nextlink = NULL)
    {
        next = nextlink;
    }
};
/*****通用单链表结点类*****/

/*****通用单链表类*****/
template <class Elem>
class LinkList
{
public:
    Link<Elem> *head; //头结点
    LinkList()
    {
        //*head = new Link<Elem>();
        head = new Link<Elem>();
    }
};
/*****通用单链表类*****/

/*****邻接表类*****/
class Graph_ADJ_List : public Graph
{
private:
    LinkList<ADJ_List_unit> *adjList;

public:
    /***构造方法***/
    Graph_ADJ_List(int numV_input) : Graph(numV_input)
    {
        adjList = new LinkList<ADJ_List_unit>[numV_input];
    }
    /***构造方法***/

    /***依附于顶点的第一条边***/
    Edge firstE(int v)
    {
        Edge tempE;
        tempE.from = v;
        Link<ADJ_List_unit> *temp = adjList[v].head;
        if (temp->next != NULL)
        {
            tempE.to = temp->next->element.terminal_vertex;
            tempE.weight = temp->next->element.weight;
        }
        return tempE;
    }
    /***依附于顶点的第一条边***/

    /***返回与e具有相同起点的下一条边***/
    Edge nextE(Edge e)
    {
        Edge tempE;
        tempE.from = e.from;
        Link<ADJ_List_unit> *temp = adjList[e.from].head;
        while (temp->next != NULL && temp->next->element.terminal_vertex <= e.to) //调整指针到当前边
        {
            temp = temp->next;
        }
        if (temp->next != NULL)
        {
            temp = temp->next;
            tempE.to = temp->element.terminal_vertex;
            tempE.weight = temp->element.weight;
        }
        return tempE;
    }
    /***返回与e具有相同起点的下一条边***/

    /***为图设置一条边***/
    void setE(int from, int to, int weight)
    {
        Link<ADJ_List_unit> *temp = adjList[from].head;
        while (temp->next != NULL && temp->next->element.terminal_vertex < to)
        {
            temp = temp->next;
        }

        if (temp->next == NULL)
        {
            temp->next = new Link<ADJ_List_unit>;
            temp->next->element.terminal_vertex = to;
            temp->next->element.weight = weight;
            numE++;
            in_degree[to]++;
            return;
        }

        if (temp->next->element.terminal_vertex == to)
        {
            temp->next->element.weight = weight;
            return;
        }

        if (temp->next->element.terminal_vertex > to)
        {
            Link<ADJ_List_unit> *other = temp->next;
            temp->next = new Link<ADJ_List_unit>;
            temp->next->element.terminal_vertex = to;
            temp->next->element.weight = weight;
            temp->next->next = other;
            numE++;
            in_degree[to]++;
            return;
        }
    }
    /***为图设置一条边***/
};
/*****邻接表类*****/